package com.datastructure.test.reverselistnode;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        Solution solution = new Solution();
        solution.reverseBetween(listNode,2,4);
    }
    public ListNode ReverseList(ListNode head) {
        ListNode newListNode = head;
        int [] array = new int[getLength(newListNode)];
        int j =0;
        ListNode initListNode = new ListNode(0);
        ListNode initNode=initListNode;
        while(newListNode!=null){
            array[j]=newListNode.val;
            j++;
            newListNode = newListNode.next;
        }
        for(int i = array.length-1;i>=0;i--){
            while(initNode.next!=null){
                initNode=initNode.next;
            }
            initNode.next=new ListNode(array[i]);
        }
        return initListNode.next;
    }

    public int getLength(ListNode head){
        int length = 0;
        while(head!=null){
            length++;
            head = head.next;
        }
        return length;
    }

    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        if(head.next==null||(m==n)){
            return head;
        }
        ListNode first = findListNode(head,m-1);
        ListNode last = findListNode(head,n+1);
        if (first!=null&&last!=null){
            ListNode lastLocation = findListNode(head,n);
            ListNode lastNode=null;
            lastLocation.next=null;
            ListNode listNode = ReverseList(first.next);
            first.next=listNode;
            while (listNode!=null){
                lastNode=listNode;
                listNode=listNode.next;
            }
            assert lastNode != null;
            lastNode.next=last;
            return head;
        }
        if(first==null&&last!=null){
            ListNode lastLocation = findListNode(head,n);
            lastLocation.next=null;
            ListNode lastNode=null;
            ListNode listNode = ReverseList(head);
            ListNode listNode1=listNode;
            while (listNode1!=null){
                lastNode=listNode1;
                listNode1=listNode1.next;
            }
            assert lastNode != null;
            lastNode.next=last;
            return listNode;
        }
        if(first != null){
            first.next=ReverseList(first.next);
            return head;
        }
        return ReverseList(head);

    }

    public ListNode findListNode(ListNode data,int location){
        int length=1;
        ListNode result = null;
        if(location==0||location==(getLength(data)+1)){
            return null;
        }
        if (location==1){
            return data;
        }
        while (data.next!=null){
            length++;
            data=data.next;
            if(length==location){
                result=data;
                break;
            }
        }
        return result;
    }


}
